package com.hao.sort;

import java.util.Random;

/**
 * @Description: TODO 冒泡排序
 * @author: a'hao
 * @date: 2021/5/7
 */
public class BubbleSort {

    public static void main(String[] args) {
        // 从0-10000中获取10000个元素的数组
        Integer[] arr = SortUtils.getRandomArr(500000, 500000);
        long start1 = System.currentTimeMillis();
        improveSort(arr);
        long end1 = System.currentTimeMillis();
        System.out.println("花费时间："+(end1-start1));
    }
    /**
     * @Author a'hao
     * @Description //TODO 对数组arr进行排序
     * @Date 19:49 2021/5/7
     * @Param [arr]
     * @return void
     **/
    public static void sort(Integer[] arr) {
        // 进行n-1次扫描交换
        for (int i = 0; i < arr.length-1; i++) {
            // 扫描交换
            for (int j = 0; j < arr.length-1; j++) {
                // 获取当前元素的值
                int temp = arr[j];
                // 如果大于后面元素的值就交换
                if (temp > arr[j + 1]) {
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    /**
     * @Author a'hao
     * @Description //TODO 优化后的排序
     * @Date 20:59 2021/5/7
     * @Param [arr]
     * @return void
     **/
    public static void improveSort(Integer[] arr){
        // 用于判断是否已经有序的便利
        boolean isSort = true;
        // n-1次扫描交换
        for (int i = 0; i < arr.length-1; i++) {
            // 扫描交换，每次扫描后就不再扫描已经有序的元素。arr.length-i-1
            for (int j = 0; j < arr.length-i-1; j++) {
                // 获取当前元素的值
                int temp = arr[j];
                // 如果大于后面元素的值就交换
                if (temp > arr[j+1]){
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    // 如果有交换就表示数据不是有序的
                    isSort = false;
                }
            }
            // 判断数据是否有序，有序就终极扫描，排序完毕
            if (isSort){
                break;
            }else {
                isSort = true;
            }
        }
    }
    public static void recursionSort(Integer[] arr){
        sort(arr,0);
        
    }

    private static void sort(Integer[] arr,Integer n){
        if (arr.length < n){
            return;
        }else {
            if (!scanExchange(arr,n)){
                sort(arr,n+1);
            }
        }
    }

    /**
     *  扫描交换
     * @param arr
     * @param n 第几次扫描交换
     */
    private static boolean scanExchange(Integer[] arr,Integer n){
        boolean isSort = true;
        for (int i = 0; i < arr.length-n-1; i++) {
            int temp = arr[i];
            if (temp > arr[i+1]){
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                isSort = false;
            }
        }
        return isSort;
    }
}
